package backtrace

import (
	"fmt"
)

func permute(nums []int) [][]int {
	ans := [][]int{}

	var backtrace func(cur int)
	backtrace = func(cur int) {
		if cur == len(nums) {
			fmt.Printf("nums: %v\n", nums)
			ans = append(ans, append([]int{}, nums...))
			return
		}
		for i := cur; i < len(nums); i++ {
			nums[i], nums[cur] = nums[cur], nums[i]
			backtrace(cur + 1)
			nums[i], nums[cur] = nums[cur], nums[i]
		}
	}

	backtrace(0)
	return ans
}

func subsets(nums []int) [][]int {
	res := make([][]int, 0)
	var backtrace func(sub []int, cur int)

	backtrace = func(sub []int, cur int) {
		res = append(res, append([]int{}, sub...))
		if cur == len(nums) {
			return
		}
		for i := cur; i < len(nums); i++ {
			sub = append(sub, nums[i])
			backtrace(sub, i+1)
			sub = sub[:len(sub)-1]
		}
	}
	backtrace([]int{}, 0)
	return res
}
